package elementaryAlgorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 郭辉
 * @className TODO
 * @description 16. 最接近的三数之和
 * 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
 *
 * 返回这三个数的和。
 *
 * 假定每组输入只存在恰好一个解。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [-1,2,1,-4], target = 1
 * 输出：2
 * 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
 * 示例 2：
 *
 * 输入：nums = [0,0,0], target = 1
 * 输出：0
 *
 *
 * 提示：
 *
 * 3 <= nums.length <= 1000
 * -1000 <= nums[i] <= 1000
 * -104 <= target <= 104
 * 通过次数
 *
 * @date 2023/4/10 9:19
 * @company 海康威视
 * @since 1.0.0
 */
public class Leet16 {
    int res;
    boolean flag = false;
    public int threeSumClosest(int[] nums, int target) {
        if (nums.length == 3){
            return nums[0]+nums[1]+nums[2];
        }
        res = Integer.MAX_VALUE;
        doublePointer(nums,new ArrayList<>(),target);
        return res;
    }
    //选择
    //路径
    //返回条件
    public void dfs(int[] nums, List<Integer> track, int target){
        //返回条件
        if (track.size() == 3){
            int tem = 0;
            for (int i = 0; i < track.size(); i++) {
                tem += nums[track.get(i)];
            }
            if (tem == target){
                res = tem;
                flag = true;
                return;
            }
            if (Math.abs(tem - target) < Math.abs(res-target)){
                res =tem;
            }
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (flag == true){
                break;
            }
            //剪枝
            if (track.contains(i)){
                continue;
            }
            //选择
            track.add(i);
            dfs(nums,track,target);
            //撤销
            track.remove(track.size()-1);
        }
    }
    public void doublePointer(int[] nums, List<Integer> track, int target){
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int l = i+1, r = nums.length-1;
            while (l < r){
                int tem = nums[i] + nums[l] + nums[r];
                //如果找到相等的，则一定是最小的，直接返回
                if (tem == target){
                    res = tem;
                    return;
                }
                if (Math.abs(tem - target) < Math.abs(res - target)){
                    res = tem;
                }
                if (tem > target){ //右指针左移
                    r--;
                }else { //左指针右移
                   l++;
                }
            }
        }
    }


    public static void main(String[] args) {
        int [] param = {1,1,1,1};
        Leet16 leet16 = new Leet16();
        int i = leet16.threeSumClosest(param,  0);
        System.out.println(i);
    }
}
